package com.yuren.codecrushlearn.Q5300;

import java.util.PriorityQueue;

/**
 * Created with Intellij IDEA.
 * Description:
 * 大根堆与小根堆结合，找中位数
 * @author 10204
 * @date 2025-05-18 21:30
 */
public class Q5334 {
    private final PriorityQueue<Integer> maxHeap; // 大根堆，存储较小的一半
    private final PriorityQueue<Integer> minHeap; // 小根堆，存储较大的一半

    public Q5334() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a); // 大根堆，按降序排列
        minHeap = new PriorityQueue<>(); // 小根堆，按升序排列
    }

    public void add(int value) {
        if (maxHeap.isEmpty() || value <= maxHeap.peek()) {
            maxHeap.offer(value);
        } else {
            minHeap.offer(value);
        }

        // 平衡两个堆的大小，数量相等时，取较小的一个，因此保持大根堆 maxHeap.size() = minHeap.size() 或者minHeap.size() + 1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public int getMiddle() {
        if (maxHeap.isEmpty()) {
            return -1;
        }
        return maxHeap.peek();
    }
}
